\section{Polynomial Factorization}

Factoring polynomials over a field is an interesting problem that arises in many applications such as algebraic coding theory. For instance, factors of $x^{n}-1$ can be used as generators of cyclic codes. One of the most well-known and oldest algorithms is Berlekamp's algorithm. Berlekamp's algorithm has a linear algebra and vector space-based approach. More recently, Cantor and Zassenhaus introduced an abstract algebra-based probabilistic algorithm which is studied in this section.\\

Given a polynomial $f(x) \in F_{q}[x]$, where $q$ is a prime power, the Cantor-Zassenhaus algorithm performs the following steps:
\begin{enumerate} 
	\item[step 1:]	Make $f(x)$ square-free.
	\item[step 2:]	Distinct Degree Factorization (DDF): split $f(x)$ into polynomials whose factors are of the same degree.
	\item[step 3:]	Equal Degree Factorization (EDF): find factors of each polynomial from the previous step.
\end{enumerate}

Let's consider the polynomial $f(x)=(x^{3}+x+1)^{2}(x^{2}+x+1)(x^{2}+1)(x+1)$ over $F_{2}$. The following show the outcome of the Cantor-Zassenhaus algorithm in each step:

\begin{enumerate} 
	\item[input:]	$f(x)=(x^{3}+x+1)^{2}(x^{2}+x+1)(x^{2}+1)(x+1)$ 
	\item[step 1:]	$f(x) = (x^{3}+x+1)(x^{2}+x+1)(x^{2}+1)(x+1)$
	\item[step 2:]	$g_{3}(x) = x^{3}+x+1$, $g_{2}(x)=(x^{2}+x+1)(x^{2}+1)$, and $g_{1}(x)=x+1$
	\item[step 3:]	$f_{2_{1}}(x)=x^{2}+1$ and $f_{2_{2}}(x)=x^{2}+x+1$
	\item[output:]	$g_{3}(x)$,$g_{1}(x)$,$f_{2_{1}}(x)$, and $f_{2_{2}}(x)$
\end{enumerate}

These steps are explored in more detail in the following sections.

\subsection{Square-free factorization}
A polynomial $f(x)$ is square-free if $gcd(f(x)/g(x),g(x))=1$ for some $g(x)$ such that $g(x)|f(x)$. The gcd can be computed using Euclid's algorithm. To see how a polynomial can be made square-free, let's make the following observation. Assume:
\[
f(x)=g^{2}(x)h(x).
\]
Taking the derivative of both sides we get:
\[
f^{'}(x)=2g(x)g^{'}(x)h(x)+g^{2}(x)h^{'}(x).
\]
Now note that:
\[
gcd(f(x),f^{'}(x))=g(x)
\]
Based on this observation, the following algorithm \cite[p. 340]{book:Geddes94} can be used for square-free factorization.




\subsection{Distinc Degree Factorization (DDF)}

For Distinct Degree Factorization (DDF), two useful theorems \cite[p. 369]{book:Gathen2003} from the discussion of polynomials over finite fields is utilized which is stated here.

\begin{Thrm} [Fermat's Little Theorm]
For nonzero $a \in F_{q}$, we have $a^{q-1}=1$, and for all $a \in F_{q}$ we have
\[
x^{q}-x = \prod_{a \in F_{Q}} (x-a) \text{ in } F_{q}[x]
\]
\end{Thrm}

\begin{Thrm}
For any $d \geq 1$, $x^{q^{d}}-x \in F_{q}[x]$ is the product of all monic irreducible polynomials in $F_{q}[x]$ whose degree divides $d$.
\end{Thrm}

Using the theorems stated above, to DDF a squre-free polynomial, one can iteratively start with $d=1$ above up to half the degree of the polynomial of interest and find the greatest common divisor (gcd) between $x^{q^{d}}-x$ and the polynomial. The non-costant results are distinct factors of the polynomial. This process is given by the following algorithm \cite[p. 369]{book:Gathen2003}:


\subsection{Equal Degree Factorization (EDF)}

Let $g_{i}(x)$ be a DDF polynomial whose factors are all of degree $i$. By a similar arguement as above, let $v(x)$ be any polynomial, now since $v(x)^{q^{i}}-v(x)$ is a multiple of all irreducible polynomials of degree $i$, then it follows that $g_{i}(x)$ factors as \cite[p. 371]{book:Geddes94}:
\[
g_{i}(x)=gcd(g_{i}(x),v(x)) \times gcd( g_{i}(x),v(x)^{ \frac{q^{i}-1}{2} } -1) \times gcd( g_{i}(x) , v(x)^{ \frac{q^{i}-1}{2} }+1)
\]
when $q$ is odd.\\

If $q$ is a power of $2$, then we have \cite[p. 373]{book:Geddes94}:
\[
g_{i}(x)=gcd(g_{i}(x),Tr(v(x))) \times gcd(g_{i}(x),Tr(v(x))+1)
\]
where $Tr(x)= x + x^{q} + \dots + x^{q^{m}-1}$ over $F_{q^{m}}$.\\

The procedure to perform EDF is summarized in the following algorithm \cite[p. 373]{book:Geddes94}:

   






